package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         287,
		Discription: "在值在1...n的n+1个数中找出重复的那个数，不能修改数组元素",
		Level:       2,
		Labels: map[string]int{
			"快慢指针": 1,
			"链表": 1,
		},
	})
}

//至少有一个元素被两个节点指，这个节点就是入环点
//转化为入环点问题
func FindDuplicate(nums []int) int {
	//没有人会指向0，所以0是链表头
	fast := 0
	slow := 0
	for {
		fast = nums[nums[fast]]
		slow = nums[slow]
		if fast == slow {
			break
		}
	}

	temp := 0
	for temp != slow {
		temp = nums[temp]
		slow = nums[slow]
	}

	return temp
}